package com.leetcode.algorithm.y22.m09.w3;

/**
 * 1971. 寻找图中是否存在路径
 * 
 * https://leetcode.cn/problems/find-if-path-exists-in-graph/
 * 
 * @author jie.deng
 *
 */
class Question1971Solution01 {

	public boolean validPath(int n, int[][] edges, int source, int destination) {
		int roots[] = new int[n];
		for (int i = 0; i < n; i++) {
			roots[i] = i;
		}
		for (int i = 0; i < edges.length; i++) {
			union(roots, edges[i][0], edges[i][1]);
		}
		return isConnected(roots, source, destination);
	}

	private boolean isConnected(int[] roots, int x, int y) {
		int rootX = findRoot(roots, x);
		int rootY = findRoot(roots, y);
		return rootX == rootY;
	}

	private void union(int[] roots, int x, int y) {
		int rootX = findRoot(roots, x);
		int rootY = findRoot(roots, y);
		if (rootX != rootY) {
			roots[rootX] = rootY;
		}
	}

	private int findRoot(int[] roots, int x) {
		while (x != roots[x]) {
			x = roots[x];
		}
		return x;
	}

}